/**
 * 孩子们的游戏(圆圈中最后剩下的数)
 *
 * 描述
 *     每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。
 *     其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们
 *     的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。
 *     每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼
 *     物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数...
 *     .这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，
 *     请你试着想下，哪个小朋友会得到这份礼品呢？
 *
 * 数据范围：
 * 1≤n≤5000，
 * 1≤m≤10000
 *
 * 要求：
 * 空间复杂度O(1)，
 * 时间复杂度O(n)
 */

/**
 * 这一题使用了动态规划, 我们最后使用空间优化的方式使空间复杂度保持在 O(1)
 * dp[i] : i 个小孩中获胜小孩的下标
 * dp[i] = (dp[i - 1] + m) % i;
 * 这个转态转移方程是怎么来的呢?
 * 首先我们知道第一次删除小孩的时候, 后面小孩数会变成 n - 1, 然后 dp[n] 获胜就可以看成有偏移量的 dp[n - 1] 中获胜的下标
 * 这个偏移量是多少呢 ? 其实就是 m 了. 我们化一个图, 一开始删除 m - 1, 然后 m 就对应 0了, 我们从 前面一个来, 所以就是要
 * 加上 m, 但是我们的是一个环呀, 最后从 n - 1 变到 0, 是会有变化的, 画图可以知道 我们正好 可以 % n 得到对应下标
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int LastRemaining_Solution (int n, int m) {
        // write code here
        // 由于后面一个状态只需要前一个的状态, 所以我们可以优化空间复杂度
        // n == 1 直接返回 0
        int f = 0;
        for (int i = 2; i <= n; i++) {
            f = (f + m) % i;
        }
        return f;
    }
}